class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        //如果面试题不让你用递归方式，以下是非递归，借助栈实现
        //用迭代方式实现后序遍历
        TreeNode* p=NULL;
        stack<TreeNode*> s;
        vector<int> vec;
        s.push(root);//把根节点入栈
        //按前序遍历的思想遍历
        while(!s.empty())//当栈不为空时进行操作
        {
            //先出栈
            p=s.top();
            s.pop();
            if(p)//不为空的话就加入vec
            {
                vec.push_back(p->val);
            }
            else
            {
                continue;
            }
            /*
            s.push(p->right);
            s.push(p->left);
            前序遍历一定要先进右节点，右节点才能后出，这是栈的性质
            这是按前序的代码，得到的是“中左右”，把这两行代码颠倒一下，得到的便是“中右左”
            中右左，反转一下不就是后序“左右中”了吗
            */
            s.push(p->left);
            s.push(p->right);
        }
        reverse(vec.begin(),vec.end());//反转
        return vec;
    }

};